The invention is related to cache memory and, in particular, to a method and apparatus for dynamically switching a cache memory from direct-mapped to set associativity.
Generally, a microprocessor operates much faster than main memory can supply data to the microprocessor. Therefore, many computer systems temporarily store recently and frequently used data in smaller, but much faster cache memory. Cache memory may reside directly on the microprocessor chip (Level 1, or L1, cache) or may be external to the microprocessor (Level 2, or L2, cache).
Referring to FIG. 1, a typical computer system includes a microprocessor (10) having, among other things, a CPU (12), a load/store unit (14), and an on-board cache memory (16). The microprocessor (10) is connected to a main memory (18) that holds data and program instructions to be executed by the microprocessor (10). Internally, the execution of program instructions is carried out by the CPU (12). Data needed by the CPU (12) to carry out an instruction are fetched by the load/store unit 14. Upon command from the CPU (12), the load/store unit (14) searches for the data first in the cache memory (16), then in the main memory (18). Finding the data in the cache memory is referred to as a xe2x80x9chit.xe2x80x9d Not finding the data in the cache memory is referred to as a xe2x80x9cmiss.xe2x80x9d
The hit rate depends, in no small part, on the caching scheme or policy employed by the computer system, e.g., direct-mapped, or set associative. Generally, a set associative caching policy provides a higher hit rate than a direct-mapped policy. However, for some computer applications, a direct-mapped policy may provide better system performance due to a better hit rate. This depends on the address sequences used by the application, the allocation of memory pages to an application by the operating system, and whether virtual or physical addresses are used for addressing the cache.
An example of a direct-mapped cache memory is functionally depicted in FIG. 2A. In this example, a portion of the main memory (18) is stored or cached in a cache memory (20) having a tag part (22) and a data part (24). The tag part (22) and the data part (24) may be a single cache memory logically partitioned into two parts, or two actual, physical cache memories. In general, the tag part (22) stores the physical addresses of the locations in main memory being cached, and the data part (24) stores the data residing in those locations. Both the tag part (22) and the data part (24) share a common index that is used to reference the two parts.
In operation, the CPU requests data by issuing to the load/store unit an address which includes an index component and a tag component. The load/store unit then goes to the tag part (22) of the cache (20) and checks the specified index to see if that particular tag entry matches the specified tag. If yes, a hit has occurred, and the data corresponding to the specified index is retrieved and provided to the CPU. If no, then the requested data has to be obtained from main memory. For example, an address having an index component of xe2x80x980xe2x80x99 and a tag component of xe2x80x9832xe2x80x99 will result in a hit, and data xe2x80x98Axe2x80x99 will be retrieved and sent to the CPU. However, there can only be one tag entry per index number and, therefore, a subsequent index component of xe2x80x980xe2x80x99 and a tag component of xe2x80x9824xe2x80x99 will result in a miss. A set associative policy generally has a higher hit rate per access, as will be explained below.
An example of a set associative cache is functionally depicted in FIG. 2B. As in the previous example, a cache memory (26) is partitioned into a tag part (28) and a data part (30), with both parts sharing a common index. However, instead of a single entry per index, the tag part (28) and the data part (30) each have four entries, best shown here as rows and columns. A row of entries is called a xe2x80x9csetxe2x80x9d so that there are as many sets as there are index numbers, and a column of entries is called a xe2x80x9cwayxe2x80x9d so that there are four ways for each index number. This particular cache policy, therefore, is commonly referred to as 4-way set associative. Those skilled in the art will appreciate that the set associative policy is commonly, but not limited to, 2-way to 8-way. Herein, examples are presented for 4-way set associativity, but the concepts are equally applicable to n-way set associativity.
In operation, when the load/store unit goes to search the tag part (28) at the specified index number, all four ways are compared to the specified tag component. If one of the four ways matches (a hit occurs), the corresponding way of the corresponding set in the data part (30) is sent to the CPU. Thus, in the previous example, a virtual address having an index component of xe2x80x980xe2x80x99 and tag component of xe2x80x9824xe2x80x99 will be a hit because there are four tag entries per index number. If the first tag entry does not match, there are three more chances to find a match per access. Thus, effectively, the 4-way set associative policy allows the CPU to find cached data one of four ways.
As mentioned previously, cache memory may contain data already residing in main memory or new data generated by the microprocessor to be written later to main memory. Stale or outdated data are xe2x80x9cflushedxe2x80x9d from cache memory because of the need to replace a data block due to a miss or move all entries of a page back to main memory.
One method of flushing is by displacing the stale data with fresh data. Typically, a displacement flush is done for an entire xe2x80x9cpagexe2x80x9d or group of index numbers with all data corresponding to the index numbers being replaced. This works fine for the direct-mapped cache where there is one-to-one correspondence between index number and tag entry. However, for a set associative cache where there are multiple tag entries per index number, replacement of a block of data is determined by the replacement policy.
In general, in one aspect, the present invention is a system for dynamically switching between mapping schemes for cache. The system comprises a microprocessor; a first mapping scheme; a second mapping scheme; and switching circuitry for switching between the first mapping scheme and the second mapping scheme, wherein the microprocessor is in communication with the cache through the switching circuitry and stores information within the cache using one of the first mapping scheme and second mapping scheme.
In accordance with one or more embodiments, the system may further comprise monitoring circuitry for determining whether one of instructions and load/store operations is using the cache, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme based on which one of instructions and load/store operations is using the cache. The system may further comprise monitoring circuitry for determining whether one of instructions and load/store operations is currently using the cache; and determining whether a mapping scheme switch has been requested for one of instructions and load/store operations, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme upon request if the one of instructions and load/store operations for which a mapping scheme switch is requested is not currently using the cache.
The system may further comprise an instruction unit in the cache; monitoring circuitry for determining whether instructions are currently using the instruction unit in the cache; and determining whether an instruction mapping scheme switch has been requested, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme for instructions upon request if the instructions are not currently using the instruction unit in the cache. The system may further comprise a load/store unit in the cache; monitoring circuitry for determining whether load/store operations are currently using the load/store unit in the cache; and determining whether a load/store operation mapping scheme switch has been requested, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme for load/store operations upon request if the load/store operations are not currently using the load/store unit in the cache. The system may further comprise control circuitry for halting the load/store operations currently using the load/store unit in the cache, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme for load/store operations upon request after halting the load/store operations currently using the load/store unit in the cache.
In general, in one aspect, the present invention is a software tool for dynamically switching mapping schemes for cache. The software tool comprises a first mapping scheme; a second mapping scheme, wherein a microprocessor in communication with the cache stores information within the cache using one of the first mapping scheme and the second mapping scheme; and a program executable on the microprocessor for switching between the first mapping scheme and the second mapping scheme.
In accordance with one or more embodiments, the software tool may further comprise a program stored on computer-readable media for determining whether one of instructions and load/store operations is using the cache; and determining whether a mapping scheme switch has been requested, wherein the switching between the first mapping scheme and the second mapping scheme is based on which one of instructions and load/store operations is using the cache. The software tool may further comprise a program stored on computer-readable media for determining whether one of instructions and load/store operations is currently using the cache; determining whether a mapping scheme switch has been requested; and switching between the first mapping scheme and the second mapping scheme upon request if the one of instructions and load/store operations is not currently using the cache.
The software tool may further comprise a program stored on computer-readable media for determining whether instructions are currently using the cache; determining whether an instruction mapping scheme switch has been requested; and switching between the first mapping scheme and the second mapping scheme upon request for instructions if the instructions are not currently using the cache. The software tool may further comprise a program stored on computer-readable media for determining whether load/store operations are currently using the cache; determining whether a load/store operation mapping scheme switch has been requested; and switching between the first mapping scheme and the second mapping scheme for load/store operations upon request if the load/store operations are not currently using the cache. The software tool may further comprise a program stored on computer-readable media for halting the load/store operations currently using the cache; and switching between the first mapping scheme and the second mapping scheme for load/store operations upon request after the load/store operations currently using the cache are halted.
In general, in one aspect, the present invention is a method for dynamically switching mapping schemes for cache. The method comprises providing a first mapping scheme; providing a second mapping scheme, wherein a microprocessor in communication with the cache stores information within the cache using one of the first mapping scheme and the second mapping scheme; and switching between the first mapping scheme and the second mapping scheme.
In accordance with one or more embodiments, the method may further comprise determining whether one of instructions and load/store operations is using the cache; and wherein the switching between the first mapping scheme and the second mapping scheme is based on which one of instructions and load/store operations are using the cache. The method may further comprise determining whether one of instructions and load/store operations is currently using the cache; determining whether a mapping scheme switch has been requested; and switching between the first mapping scheme and the second mapping scheme upon request if the one of instructions and load/store operations is not currently using the cache.
The method may further comprise determining whether instructions are currently using the cache; determining whether an instruction mapping scheme switch has been requested; and switching between the first mapping scheme and the second mapping scheme for instructions if the instructions are not currently using the cache. The method may further comprise determining whether load/store operations are currently using the cache; determining whether a load/store operation mapping scheme switch has been requested; and switching between the first mapping scheme and the second mapping scheme for load/store operations if the load/store operations are not currently using the cache. The method may further comprise halting the load/store operations currently using the cache; and switching between the first mapping scheme and the second mapping scheme for load/store operations upon request after the load/store operations currently using the cache are halted.
In general, in one aspect, the present invention is an apparatus for dynamically switching mapping schemes for cache. The apparatus comprises a microprocessor; a first mapping scheme; a second mapping scheme, wherein a microprocessor in communication with the cache stores information within the cache using one of the first mapping scheme and the second mapping scheme; and means for switching between the first mapping scheme and the second mapping scheme.
In accordance with one or more embodiments, the apparatus may further comprise determining whether one of instructions and load/store operations is using the cache; and means for switching between the first mapping scheme and the second mapping scheme based on which one of instructions and load/store operations is using the cache. The apparatus may further comprise means for determining whether one of instructions and load/store operations is currently using the cache; means for determining whether a mapping scheme switch has been requested; and means for switching between the first mapping scheme and the second mapping scheme upon request if the one of instructions and load/store operations is not currently using the cache.
Advantages of the present invention may include one or more of the following. In one or more embodiments, the present invention allows dynamic switching between direct mapping and set associative mapping of cache. Mapping modes can be switched without flushing the cache or restarting the system. This allows the instruction or data caching policy to be switched without affecting the other. Displacement flushing can be used straightforwardly while in direct mapping mode. The present invention determines whether instructions or load/store operations are accessing the cache prior to switching and thus, prevents mid-line replacement switching errors. The present invention halts load/store operations prior to switching allowing anytime dynamic switching for a load/store unit in the cache. Other advantages and features will become apparent from the following description, including the figures and the claims.